package com.huhu.sort;

public class MergeSort {

    public static void mergeSort(int arr[],int l,int mid,int r){
        //复制一份数组
        int arrcopy[]=new int[r-l+1];
        //标定零界点
        int i=l;
        int j=mid+1;
        int k=0;

        while(i<=mid &&j<=r){
            if(arr[i]<=arr[j]){
                arrcopy[k++]=arr[i++];
            }else{
                arrcopy[k++]=arr[j++];
            }

        }
        //归并排序有可能分的不均等
        while(i<=mid){
            arrcopy[k++]=arr[i++];
        }
        while(j<=r){
            arrcopy[k++]=arr[j++];
        }
        //k=r-1+1-1
        for(int m=0;m<k;m++){
            arr[l++]=arrcopy[m];
        }
        arrcopy=null;

    }

    public static void upTodown(int arr[],int l,int r){
        if(l>=r || arr==null){
            return;
        }
        int mid =(l+r)/2;
        upTodown(arr,l,mid);
        upTodown(arr,mid+1,r);


        //partition
        mergeSort(arr,l,mid,r);
    }

    public static void main(String[] args) {
        int i;
        int[] a = {5,6,5,4,3,2,1,0};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
        System.out.printf("\n");

        upTodown(a,0,a.length-1);

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
        }
        System.out.printf("\n");
    }


}
